package leetcode_901_1000;

import sun.awt.image.PixelConverter;

import java.util.Arrays;

public class LeeCode_948 {
    public static void main(String[] args) {
        System.out.println(bagOfTokensScore(new int[]{100, 200, 300, 400}, 200));
        System.out.println(bagOfTokensScore(new int[]{100, 200}, 150));
    }
    private static int bagOfTokensScore(int[] tokens, int power) {
        int n = tokens.length;
        if (n == 0)
            return 0;
        Arrays.sort(tokens);
        int l = 0, r = n - 1, ans = 0;
        if (power < tokens[0])
            return 0;
        int sum = 0, get = 0;
        for (int i = l; i <= r; i++) {
            sum += tokens[i];
            if (sum > power){
                break;
            }
            get++;
        }
        ans = Math.max(ans, get);
        while (l < r && power >= tokens[l]){
            power += tokens[r] - tokens[l];
            l++;
            r--;
            sum = 0;
            get = 0;
            for (int i = l; i <= r; i++) {
                sum += tokens[i];
                if (sum > power){
                    break;
                }
                get++;
            }
            ans = Math.max(ans, get);
        }
        return ans;
    }
}
